package com.huo.linked;


/**
 * 双向链表也是链表的一种，它每个数据结点中都有两个结点，分别指向其直接前驱和直接后继h
 *
 * @param <E>
 */
public class LinkedList<E> {
    /**
     * 头节点
     */
    private Node<E> first;
    /**
     * 尾节点
     */
    private Node<E> last;

    /**
     * 大小
     *
     * @return
     */
    private int size;


    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 在结尾添加元素
     *
     * @param e
     * @return
     */
    public boolean add(E e) {
        /**
         * 记录下尾节点，当在结尾插入时，插入的是尾节点后面
         * 尾节点的next指向新添加的节点
         */
        Node<E> node = last;
        //创建新节点
        Node<E> newNode = new Node<>(null, node, e);
        //把newNode设置为尾结点
        last = newNode;
        //如果size为0，newNode既是头节点也是尾节点
        if (size == 0) {
            first = newNode;
        } else {
            node.setNext(newNode);
        }
        size++;
        return true;
    }


    /**
     * 根据元素获取链表中的节点
     *
     * @param index
     * @return
     */
    public Node<E> getNode(int index) {
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            //获取当前节点的下一个节点
            node = node.getNext();
        }
        return node;
    }

    /**
     * 移除下标元素的节点
     *
     * @param index
     */
    public void remove(int index) {
        if(isEmpty()){
            throw new NullPointerException("链表中没元素！");
        }
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("链表没这个多元素");
        }
        size--;
        //获取要删除的结点
        Node<E> node = getNode(index);
        Node<E> pre = node.getPre();
        Node<E> next = node.getNext();
        //如果是头结点
        if (node.getPre() == null) {
            first = next;
        } else {
            /**
             * 不是头节点的话，前节点的next指向当前节点的下一个节点
             */
            pre.setNext(next);
            //将当前节点的pre指向删掉
            node.setPre(null);
        }
        //如果是尾结点
        if (node.getNext() == null) {
            last = pre;
        } else {
            /**
             * 如果不是尾结点的话，下一个节点的前节点指向前一个节点
             */
            next.setPre(pre);
            //将当前节点的next指向删掉
            node.setNext(null);
        }

    }

    /**
     * 大小
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 获取下标的节点
     *
     * @param index
     * @return
     */
    public E get(int index) {
        if(isEmpty()){
            throw new NullPointerException("链表中没元素！");
        }
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("链表没这个多元素");
        }
        return getNode(index).getE();
    }

    /**
     * 在头添加元素
     *
     * @param e
     */
    public void addFirst(E e) {
        Node<E> node = first;
        Node<E> newNode = new Node<>(node, null, e);
        first = newNode;
        //如果size为0，newNode既是头节点也是尾节点
        if (size == 0) {
            last = newNode;
        } else {
            node.setPre(newNode);
        }
        size++;
    }

    /**
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("下标错误啦！");
        }
        if (index == 0) {
            addFirst(e);
        } else if (index == size - 1) {
            add(e);
        } else {
            size++;
            //获取当前下标的节点，该节点的前节点的next指向新节点，新节点的next指向该节点
            Node<E> node = getNode(index);
            Node<E> pre = node.getPre();
            //新节点
            Node<E> newNode = new Node<>(node, pre, e);
            pre.setNext(newNode);
            node.setPre(newNode);
        }
    }



    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.add("4");
        linkedList.add("6");
        linkedList.add(3,"5");
        linkedList.remove(4);
        System.out.println(linkedList.get(0));
        System.out.println(linkedList.get(1));
        System.out.println(linkedList.get(2));
        System.out.println(linkedList.get(3));
        System.out.println(linkedList.get(4));

    }
}
